package violencerecursion;

/**
 * @author tongchen
 * @create 2023-03-21 16:37
 */
public class NEmpress {
    public static void main(String[] args) {
        //创建date
        int n=4;
        int[]data=new int[n];
        System.out.println(process(data, 0, n));


    }
    //创建递归过程
    public static int process(int[]data,int i,int n){
        //判断出口条件:共有n个元素，一旦当前行越过了n-1，则说明成功
        if(i==n){
            return 1;
        }
        //循环处理每一列
        //如果没结束
        int res=0;
        for(int j=0;j<n;++j){
            //判断当前元素是否有效
            if(isValid(data,i,j)){
                data[i]=j;
                //进入下一层递归
               res+= process( data, i+1, n);
            }
        }
        return res;
    }
    //递归1和递归2在逻辑上是一致的，但是不同的地方在于检验操作，递归1使用data数组进行检验，但是递归2是用位运算数决定
public static int process2(int limit,int col,int leftLim,int rightLim){
        //递归出口
    if(limit==col){
        return 1;
    }
    //检查能放的位置
    int pos= limit&(~(col|leftLim|rightLim));
    int mostRight=0;
   int res=0;
    //检验是否能递归
    while(pos!=0){
        //找最右的位置
         mostRight=pos&(~pos+1);
        //如果可以递归就更新
        pos-=mostRight;
      res+=  process2(limit,col|mostRight,(leftLim|mostRight)<<1, (rightLim|mostRight)>>>1);
    }
    return res;
}
    private static boolean isValid(int[] data, int i, int j) {
        //在data中检验是否存在
        for(int k=0;k<i;++k){
            if(data[k]==j||(Math.abs(i-k)==Math.abs(j-data[k]))){
                return false;
            }
        }
        return true;
    }
}
